package com.mdnote.jianzhi_offer.linked_list;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/11/10 0:42
 * @Email rhythm_2019@163.com
 * @Description 剑指 Offer 22. 链表中倒数第k个节点
 */
public class Offer22 {
    public ListNode getKthFromEnd(ListNode head, int k) {
        if (head == null) {
            return null;
        }
        ListNode fast = head, slow = head;

        // 先让快指针走到第k个节点
        for (int i = 1; i < k; i++) {
            if (fast.next == null) {
                return null;
            }
            fast = fast.next;
        }

        // 同时移动两个指针
        while (fast.next != null) {
            slow = slow.next;
            fast = fast.next;
        }

        return slow;
    }

    public static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
    }
}
